package pers.tz.题目.leetcode;

import com.sun.java.swing.plaf.windows.WindowsDesktopIconUI;

import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author irony
 * @date 2024-03-10
 */
public class leetcode_0014_最长公共前缀 {
//编写一个函数来查找字符串数组中的最长公共前缀。
//
// 如果不存在公共前缀，返回空字符串 ""。
//
// 示例 1：
//
//输入：strs = ["flower","flow","flight"]
//输出："fl"
//
// 提示：
//
// 1 <= strs.length <= 200
// 0 <= strs[i].length <= 200
// strs[i] 仅由小写英文字母组成

    public static void main(String[] args) {
//        System.out.println(longestCommonPrefix2(new String[]{"flower", "flow", "flight"}));
//        System.out.println(longestCommonPrefix2(new String[]{"dog","racecar","car"}));
//        System.out.println(longestCommonPrefix2(new String[]{"aaa", "aa", "aaa"}));
        System.out.println(longestCommonPrefix2(new String[]{""}));
    }

    // 最优解
    public static String longestCommonPrefix2(String[] strs) {
        if (strs.length == 1) {
            return strs[0];
        }

        char[] charArray = strs[0].toCharArray();
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < strs.length; i++) {
            char[] tmp = strs[i].toCharArray();
            int index = 0;
            while (index < tmp.length && index < charArray.length) {
                if (charArray[index] != tmp[index]) {
                    break;
                }
                index++;
            }

            min = Math.min(index, min);
            if (min == 0) {
                return "";
            }
        }
        return strs[0].substring(0, min);
    }

    // 可行解
    public static String longestCommonPrefix(String[] strs) {
        StringBuilder result = new StringBuilder();

        int minLen = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            if (strs[i].length() < minLen) {
                minLen = strs[i].length();
            }
        }

        for (int i = 0; i < minLen; i++) {
            char c = strs[0].charAt(i);
            result.append(c);

            for (int j = 1; j < strs.length; j++) {
                if (c != strs[j].charAt(i) && result.length() > 0) {
                    result.deleteCharAt(result.length() - 1);
                    return result.toString();
                }
            }
        }

        return result.toString();
    }
}
